#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2021, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 0008.py
@time: 2021/9/10 14:35
@desc: https://leetcode-cn.com/problems/find-the-student-that-will-replace-the-chalk
'''
class Solution:
    def chalkReplacer(self, chalk, k: int) -> int:
        # 取余避免重复计算
        k %= sum(chalk)
        while True:
            for i in range(len(chalk)):
                if k < chalk[i]:
                    return i
                k -= chalk[i]

if __name__ == '__main__':
    s = Solution()
    chalk = [8,66,38,1,9,84,35,56,20,50,89,21,72,8,1,9,86,75,99,90,25,87,72,1,33,64,10,37,80,21,60,56,10,77,32,37,72,72,88,18,11,44,21,75,100,77,57,50,74,32,72,25,8,41,34,93,74,19,46,21,90,57,88,98,29,63,52,74,27,4,63,94,3,19,69,16,26,11,22,52,5,17,40,86,96,29]
    k = 661513648
    n = s.chalkReplacer(chalk, k)
    print(n)